package com.example.leetcode.design;

import com.example.leetcode.graph.common.GraphUtils;

class Graph {

    int[][] dist;
    int size;

    public Graph(int n, int[][] edges) {
        size = n;
        dist = new int[n][n];
        init(n, edges);
        floyd(n);
    }

    private void init(int n, int[][] edges) {
        GraphUtils.initDist(n, dist);

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            dist[from][to] = weight;
        }
    }

    private void floyd(int n) {
        GraphUtils.updateDist(n, dist);
    }

    public void addEdge(int[] edge) {
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
        if (dist[from][to] < weight) {
            return;
        }
        dist[from][to] = weight;
        for (int left = 0; left < size; left++) {
            for (int right = 0; right < size; right++) {
                if (dist[left][from] == Integer.MAX_VALUE || dist[to][right] == Integer.MAX_VALUE) {
                    continue;
                }
                dist[left][right] = Math.min(dist[left][right], dist[left][from] + dist[from][to] + dist[to][right]);
            }
        }
    }

    public int shortestPath(int node1, int node2) {
        return dist[node1][node2] == Integer.MAX_VALUE ? -1 : dist[node1][node2];
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */
public class leetcode2642 {
    public static void main(String[] args) {
        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
        Graph g = new Graph(4, edges);
        System.out.println(g.shortestPath(3, 2)); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
        System.out.println(g.shortestPath(0, 3)); // 返回 -1 。没有从 0 到 3 的路径。
        System.out.println(g.shortestPath(1, 3)); // 返回 -1 。没有从 1 到 3 的路径。
        int[] edge = {1, 3, 4};
        g.addEdge(edge); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
        System.out.println(g.shortestPath(0, 3)); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。
        System.out.println(g.shortestPath(1, 3)); // 返回 4 。从 1 到 3 的最短路径为 1 -> 3 ，总代价为 4 。
    }
}
